The present invention relates to probabilistic decision devices and more particularly to decision devices making probabilistic decisions through implementation of principles embodied in a classical probability problem termed the "Urn" problem.
The performance of Secondary Radar/IFF Sliding Window Decision Devices is very difficult to analyze theoretically. Hence, lengthy experimental "Monte Carlo" methods are usually used to determine how well such devices perform. There is a classical "urn" problem in the field of statistics and probability that is quite similar to the Secondary Radar/IFF problem, and the analytical solution to this classical problem is well-known. The Electronic Urn Decision Device (this invention) performs, at a very high rate, the functions described in the classical urn problem. Since its proper performance when prescribed inputs are provided can be determined analytically, and the above-mentioned Biased-Bit Generator will provide prescribed inputs as desired, the Electronic Urn Decision Device's performance can be checked very easily.
After it has been determined that the Electronic Urn Decision Device's performance is satisfactory, it can be used as a standard for determining how well other decision devices perform. There are at least two ways in which the effectiveness of operational decision devices can be determined by this standard device:
(1) The decision made by a device under test may be compared with those made by the standard device when the same sequence of inputs are provided to both. Note that the Biased-Bit Generator can repeat a prescribed sequence as often as desired; thus the two decision devices do not have to be treated simultaneously.
(2) The data upon which an operational decision device makes decisions may be recorded and later fed into the standard device. A comparison can then be made of the "standard" device's decisions and the "operational" device's decisions.
The second of these two ways is, of course, much more cumbersome and expensive than the first.
The basic Secondary Radar/IFF Sliding Window problem is illustrated in FIG. 1. The Shift Register (SR5) is filled with "ones" and "zeros". Each "one" represents receipt of a correct reply and each "zero" represents an incorrect reply (or no reply at all) to an interrogation. After W bits (representing the responses to W interrogations) have entered the shift register, each time a new bit is entered into the register on the right, a bit leaves the register from the left. Thus, the "ones" in the shift register always represent the correct replies received to the last W interrogations. The counter (CTR 6) maintains a continuous count of the number of "ones" in the shift register, and makes an Accept decision if and only if it reaches a preselected threshold number T.sub.A.
The probability p that a correct reply will be received may be likened to the drawing of a ball from an Urn (containing only black and white balls of equal size) in which the percentage of black balls is equal to the percentage of interrogations that produce acceptable replies (from a given target). Of course, each time a ball is drawn, it must be returned to the urn and the urn must be thoroughly shaken before another ball is drawn. Thus, we may set ##EQU1## If the shift register of FIG. 1 is replaced by an open-ended trough just long enough to hold W balls and, each time a ball is drawn from the urn, a ball of the same color is placed in one end of the trough, then after W balls have been drawn, each ball placed in the trough will force a ball out at the other end. FIG. 2, where balls are to be drawn from Urn No. 1 and then a corresponding ball of the same color placed in the trough, thus represents the sliding window problem. Decisions are made by counting the number of black balls in the trough after each new ball is placed in it. An accept decision is made each time a predetermined number T of black balls are in the trough.
It is easy to determine the probability that a black or white ball will be placed in the trough after each drawing from Urn No. 1, but since the color of the ball pushed out of the trough depends upon what happened W drawings earlier, the storage requirements for exact analysis become very difficult for large values of W. And no simple way of expressing this probability in closed form has been found. If the trough of FIG. 2 is replaced by another urn (Urn No. 2), and instead of taking a specific ball out to make room for the new one, Urn No. 2 is shaken and a ball is drawn at random from it before the new ball is put in, a new decision device will be formed. Note that since Urn No. 2 is thoroughly shaken before each ball is removed from it, the probability that a black (or white) ball will be removed depends only upon the percentage of black (or white) balls in it. If proper choices of W (the number of balls in Urn No. 2) and T.sub.A (the number of black balls needed in Urn No. 2 to produce an Accept decision) are made, then decisions corresponding to those made by the sliding window device of FIG. 1 will result. The probability of making an accept decision in N tries (where N is arbitrary) for any desired percentage of black balls in Urn No. 1 can easily be calculated by iterative use of Equations 2-4 provided below.
The probability P(X/Y) that X black balls will be in Urn No. 2 after Y trials (drawings) is given by the cumulative binomial probability distribution for Y.ltoreq.W. ##EQU2## Since Equation 1 with Y=W gives the probability of any number X (where X.ltoreq.W) of black balls in Urn No. 2 after W trials, it is necessary only to find a way of determining the probabilities that X will increase, remain the same, or decrease with the next, or (W= 1)th trial, in order to use the same procedure iteratively to determine the probability of having X black balls in Urn No. 2 after any number of trials.
The following formulas show how the correct values for P(X/Y) can be found when Y&gt;W.
If X= T.sub.A, then: ##EQU3##